package leetcode.题库.数组.双指针;

/**
 * 接雨水
 *
 * @author yanzhenming
 * @date 2023/4/11  19:17
 */

/**
 * 描述
 * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
 *
 */

/**
 * 思路
 * 双指针
 * 记录左右最大值，左右当前值
 * 左右当前值小的移动，积累的雨水为左右最大值中较小值减去当前值
 */
public class Solution42 {

    public static void main(String[] args) {
        int[] arr = new int[]{0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(arr));
    }

    public static int trap(int[] height) {
        int left = 0, right = height.length - 1, leftMax = 0, rightMax = 0, res = 0;
        while (left <= right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (height[left] < height[right]) {
                res += Math.min(leftMax, rightMax) - height[left];
                left++;
            } else {
                res += Math.min(leftMax, rightMax) - height[right];
                right--;
            }
        }
        return res;
    }

}
